Within a typical digital communications system, information is represented as a sequence of binary bits. To transmit the information, the binary bits are modulated onto an analogue signal waveform, and transmitted over a telecommunications channel. The communication channel will typically introduce noise and interference that corrupt the transmitted signal. At the receiver, the corrupted received signal is mapped back into the digital domain, but due to the introduced noise, bit errors may result.
In order to compensate for bit errors, channel coding is often used in digital communications systems to allow for error detection and correction to occur. Channel coding is most often accomplished by selectively introducing redundant bits into the transmitted bitstream. These additional bits allow detection and correction of bit errors in a received datastream. Using channel coding to obtain this effect, however, leads to a reduction in data rate, or an increase in the bandwidth required to transmit the same amount of information.
There are two main types of channel codes, being block codes and convolutional codes. Convolutional codes are one of the most widely used channel codes in practical communications systems. Convolutional codes are commonly specified by three parameters, being the number of output bits n, the number of input bits k, and the number of memory registers m. The ratio between the number of input bits and the number of output bits is called the code rate r. Typically in order to introduce redundancy into the coded bitstream; the number of output bits will be greater than the number of input bits.
There are basically two types of convolutional encoder already known in the art. FIG. 1 illustrates a first kind of encoder, which is a non-recursive encoder, wherein the output bits are dependent upon the present input bit and the previous input bits. More particularly, FIG. 1 illustrates a rate 1/2 encoder, such that two output bits are output for every input bit.
More particularly, the 1/2 rate non-recursive encoder 110 of FIG. 1 comprises an input line 116 which inputs a bitstream xn to be encoded into the encoder. One bit delays 118 and 120 are provided, such that at the input to the encoder the present bit is represented as un, the previous bit is represented after delay 118 as bit un−1, and the second previous bit which had undergone both delays 118 and 120 is represented as un−2. A first modulo-2 adder 112 is provided, as is a second modulo-2 adder 114. The respective outputs 130 and 132 from the adders 112 and 114 output the coded bitstreams y1,n and y2,n. As mentioned, because this is a rate 1/2 encoder, two output bits are obtained for every input bit.
Typically, as is well known, the configuration of a convolutional encoder is defined by what is known as a set of generator polynomials G=(g1, g2, . . . , gn) (referred to further herein as the generator matrix). More particularly, each generator polynomial g1, g2, etc. defines the inputs to the modulo-2 adders, in terms of which of the present and previous bits are input to the adders for modulo-2 addition to then be performed thereon, to produce an output. Within the example 1/2 rate non-recursive encoder of FIG. 1, the first generator polynomial is:g1(D)=1+D+D2 which means that the first modulo-2 adder 112 outputting the first coded output bit on output line 130 receives both the present input bit, plus the input bit un−1 subject to a first delay, plus the previous input bit un−2 subject to both delays 118 and 120. In FIG. 1 it can be seen that line 122 connects the present input bit to the modulo-2 adder 112, whereas line 124 connects the previous bit un−1 to the adder, and line 126 connects the bit before that un−2 to the adder.
A generator polynomial is provided for each modulo-2 adder, and hence it will be seen that in FIG. 1 a second generator polynomial g2 is provided, wherein:g2(D)=1+D2 
This means, as can be seen, that the second modulo-2 adder 114 receives the input bit un via line 128, as well as the twice delayed previous bit un−2 via line 126. The adder 114 performs modulo-2 addition on these inputs, to provide a second output bit for every input bit. As is known, to encode an input bitstream using a non-recursive encoder of the type shown in FIG. 1, the bitstream is input into the encoder one bit at a time, and the two coded bitstreams are then read out from the outputs 130 and 132. Typically, for transmission the two coded bitstreams would be interleaved to form a single bitstream.
A second type of convolutional encoder is shown in FIG. 2. This is known as a recursive convolutional encoder, wherein the coded output bits are dependent not only on the current input bit, but also on previous “state” bits. Such “state” bits are, as shown in FIG. 2, bits taken from within the internal processing of the encoder (i.e. bit un−1 in FIG. 2) and which are then fed back to the input of the encoder. Due to the feed back of previous “state” bits to the recursive encoder input, the set of generator polynomials of a recursive convolutional encoder is typically of the form:—
  G  =      (                            g          ⁢                                          ⁢          1                          g          ⁢                                          ⁢          0                    ,                        g          ⁢                                          ⁢          2                          g          ⁢                                          ⁢          0                    ,      …      ⁢                          ,              gm                  g          ⁢                                          ⁢          0                      )  
An example recursive convolutional encoder is shown in FIG. 2. Here the recursive convolutional encoder 210 comprises an input line 216 upon which an input bitstream xn to be encoded is input. The input 216 feeds into a first modulo-2 adder 234, which provides an output line wherein the result of the modulo-2 addition performed thereby is provided as bit un. un is input to a first delay 218 which has an output line 224 on which a first delayed bit un−1 is provided which inputs into a second delay 220, to provide a second delayed bit un−2, on line 226. A second modulo-2 adder 212 is provided, the output of which on line 230 provides a first coded output bit, and a third modulo-2 adder 214 is also provided, the output of which on line 232 provides the second coded output bit, for every input bit. As can be seen, the output of the first modulo-2 adder 234 is input into the second modulo-2 adder 212 via line 222, and into the third modulo-2 adder 214, via line 228. Additionally, the second modulo-2 adder 212 receives the first delayed bit un−1 via line 224, as well as the second delayed bit un−2, via line 226. The third modulo-2 adder 214 does not receive the first delayed bit un−1, but does receive the second delayed input bit un−2, via line 226. To provide the recursive operation, the first modulo-2 adder 234, in addition to receiving the input bitstream, also receives the first delayed bit un−1, via line 236. In view of the above arrangement, and as shown in FIG. 2, the generator polynomials for the recursive encoder shown in FIG. 2 are:—g0(D)=1+D; g1(D)=1+D+D2; andg2(D)=1+D2 
The encoders of FIGS. 1 and 2 relate to rate 1/2 codes i.e. one input bit produces two output bits. More generally however, rate k/n codes are also possible, where k is greater than or equal to 1, and n is greater than or equal to k such that k input bits are encoded into n output bits. Such codes are defined by a set of generator polynomials, represented as a matrix with k rows and n columns, as shown below:—
            G      RCE        ⁡          (      D      )        =      [                                                      g                              1                ,                1                                                    g                              1                ,                0                                                              …                          …                          …                                                    g                              1                ,                n                                                    g                              1                ,                0                                                                          ⋮                          ⋱                                                                                                                          ⋮                                      ⋮                                                                          ⋱                                                                          ⋮                                      ⋮                                                                                                                          ⋱                          ⋮                                                                g                              k                ,                1                                                    g                              k                ,                0                                                              …                          …                          …                                                    g                              k                ,                n                                                    g                              k                ,                0                                                          ]  
Generally speaking, within the above generator matrix, gk,n represents how the kth input contributes to the nth output, whereas gk,0 represents the feedback connection for the kth input. Each input may have a different feedback polynomial, as shown.
An example rate 2/3 recursive encoder typical of those known in the art is shown in FIG. 3. Here, the rate 2/3 recursive encoder 710 has two inputs 712 and 714, on which are respectively received input bitstreams x1,n and x2,n. The first input line 712 inputs the first bitstream x1,n into a first modulo-2 adder 716, which provides an output state bit u1,n to a first one bit delay 720. Additionally, first feed forward line 736 feeds the state bit u1,n to a second modulo-2 adder 730, whereas second feed forward line 734 feeds the state bit u1,n to a third modulo-2 adder 728. The output of the one bit delay 720 is a second state bit u1,n−1, which is fed by feed forward line 740 to the third modulo-2 adder 728, and also by feedback line 738 to the first modulo adder 716. The second state bit u1,n−1 is also fed to a second delay 722, the output of which is third state bit u1,n−2, which is fed to both the second modulo-2 adder 730, and the third modulo-2 adder 728 respectively. Thus, with respect to the state bits, the first state bit u1,n is the result of the modulo-2 addition of the present input bit x1,n and the second state bit u1,n−1; the second state bit u1,n−1 is the one bit delayed version of the first state bit u1,n; and the third state bit u1,n−2 is the one bit delayed version of the second state bit u1,n−1. The third modulo-2 adder 728 outputs a first output bit y1,n on output line 750, being the result of the modulo-2 addition of each of the first, second and third state bits fed to the third modulo-2 adder 728.
Turning to the second input line 714, on which input bits x2,n are input, a fourth modulo-2 adder 718 receives the input bitstream x2,n on line 714, and outputs a fourth state bit u2,n to a third one bit delay 724, and also, via feed forward line 746, to a fifth modulo-2 adder 732. The one bit delay 724 outputs a fifth state bit u2,n−1 to a fourth one bit delay 726, and also, via feed forward line 742 to the second modulo-2 adder 730. The second one bit delay 726 outputs a sixth, state bit u2,n−2 via line 748 to the second modulo-2 adder 730, and the fifth modulo-2 adder 732. Additionally, the sixth state bit u2,n−2 is also fed back via feedback line 744 to the fourth modulo-2 adder 718 at input 714. The second modulo-2 adder 730 therefore receives as input the following state bits: u1,n, u1,n−2, u2,n−1, and u2,n−2. Output line 752 is provided from the second modulo adder 730, on which is output an output bitstream y2,n. The fifth modulo-2 adder 732 receives the state bit u2,n and u2,n−2 as inputs, and outputs on line 754 the third output bitstream y3,n. With such an arrangement therefore, for each pair of input bits x1,n and x2,n, three output bits y1,n, y2,n, and y3,n are output. Additionally, in view of the above arrangement, and as shown in FIG. 3, the generator polynomials for the recursive rate 2/3 encoder shown in FIG. 3 are as follows:—g1,1(D)=1+D+D2;g1,2(D)=1+D2;g1,3(D)=0;g2,1(D)=0;g2,2(D)=D+D2;g2,3(D)=1+D2;g1,0(D)=1+D; andg2,0(D)=1+D2 
Recursive encoders when compared to non-recursive encoders, whilst slightly more complicated, produce a coded output which has more “weight” i.e. has better error detection and correction properties. Non-recursive convolutional codes have conventionally been used in communications systems such as GSM or the like, but recently there has been introduced a requirement for recursive convolutional codes, because of their better performance characteristics. Conventionally, for a receiver to be able to decode both a non-recursive convolutionally encoded bitstream as well as a recursive convolutionally encoded bitstream, two separate decoders are required, one for the non-recursively coded bitstream, and another for the recursively coded bitstream. Two decoders are typically required because the branch labels in the state transition diagram are different for recursive and non-recursive encoders. Thus, to decode a non-recursively encoded bitstream a decoder particularly adapted to the target non-recursive encoder which produced the bitstream has conventionally been required, and likewise, to decode a recursively encoded bitstream, a decoder particularly adapted to the operation of the target recursive encoder which produced the bitstream has been required. Where the decoders are being implemented in hardware, for example on an integrated circuit, this leads to more silicon area being required, to implement the two decoders. Clearly, therefore, it would be beneficial if the requirement to have a particular decoder for every particular type of convolutional encoding could be removed, and a single, or at least a reduced subset, of decoders provided which can be used to decode both recursive and non-recursively encoded bitstreams.